package com.leetcode.August;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Description: 每日温度 https://www.bilibili.com/video/BV1VN411J7S7/?vd_source=7a8a5dd9662050409c1b174845102e36
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-04 11:14
 */
public class LC739每日温度 {
//    public int[] dailyTemperatures(int[] temperatures) {
//        int length = temperatures.length;
//        int[] ans = new int[length];
//        Deque<Integer> st = new ArrayDeque<>();//单挑递减栈
//        for (int i = length - 1; i >= 0; i--) {
//            int t = temperatures[i];
//            while (!st.isEmpty() && t >= temperatures[st.peek()]) {
//                st.pop();//移除栈顶元素
//            }
//            if (!st.isEmpty()) {
//                ans[i] = st.peek() - i;
//            }
//            st.push(i);
//        }
//        return ans;
//    }
public int[] dailyTemperatures(int[] temperatures) {
    int length = temperatures.length;
    int[] ans = new int[length];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = length - 1; i >= 0; i--) {
        int t = temperatures[i];
        while (!st.isEmpty() && t >= temperatures[st.peek()]){
            st.pop();
        }
        if(!st.isEmpty()){
            ans[i] = st.peek() - i;
        }
        st.push(i);
    }
    return ans;
}
}
